#include<stdio.h>
void swap(int*a,int*b){
    int temp = *b;
    *b = *a;
    *a = temp;
}
void max_heapify(int unsorted_array[],int start,int end){
    int dad = start;
    int son = dad * 2 +1;
    while (son <= end){
        if(son + 1 <= end && unsorted_array[son] < unsorted_array[son +1])
            son ++;
        if(unsorted_array[dad] > unsorted_array[son])
            return;
        else{
            swap(&unsorted_array[dad],&unsorted_array[son]);
            dad = son;
            son = dad * 2 +1;
        }
    }
}
void insertion_sort(int unsorted_array[], int num_elements){
    if (num_elements<2) {
        return;
    }
    for (int i=1; i<num_elements; i++) {
        int insertValue = unsorted_array[i];//暂存需要插入元素

        int j = i-1;

        //从右向左比较元素
        for (; j>=0 && insertValue<unsorted_array[j]; j--) {
            unsorted_array[j+1] = unsorted_array[j];
        }

        unsorted_array[j+1] = insertValue;
    }
}
void QuickSort(int unsorted_array[], int left, int right)
{
    int i = left;
    int j = right;
    int temp;

    if (i <= j)
    {
        temp = unsorted_array[i];
        while (i != j)
        {

            while (temp <= unsorted_array[j] && j > i)
            {
                j--;
            }
            unsorted_array[i] = unsorted_array[j];

            while (temp >= unsorted_array[i] && j > i)
            {
                i++;
            }
            unsorted_array[j] = unsorted_array[i];
        }

        unsorted_array[i] = temp;
        QuickSort(unsorted_array,left,i-1);
        QuickSort(unsorted_array,j+1,right);
    }
}


void quick_sort(int unsorted_array[], int num_elements){
    int i = 0;
    int j = num_elements - 1;
    int temp;
    if (i <= j)
    {
        temp = unsorted_array[i];
        while (i != j)
        {

            while (temp <= unsorted_array[j] && j > i)
            {
                j--;
            }
            unsorted_array[i] = unsorted_array[j];

            while (temp >= unsorted_array[i] && j > i)
            {
                i++;
            }
            unsorted_array[j] = unsorted_array[i];
        }

        unsorted_array[i] = temp;
        QuickSort(unsorted_array, 0, i - 1);
        QuickSort(unsorted_array, j + 1, num_elements-1);
    }
}


void heap_sort(int unsorted_array[], int num_elements) {
    int i;
    //初始化，i从最后一个父节点开始
    for(i=num_elements/2-1;i>=0;i--)
        max_heapify(unsorted_array,i,num_elements-1);
    //先将第一个元素和已排好元素前一位做交换，再重新调整，直到排序完毕
    for(i=num_elements-1;i>0;i--)
    {
        swap(&unsorted_array[0],&unsorted_array[i]);
        max_heapify(unsorted_array,0,i-1);
    }
}

void main() {
    int a[] = {1,9,8,7,6,5,0,2,3,4};

    insertion_sort(a, 10);

    for(int i=0; i<10; i++) {
        printf("%d ", a[i]);
    }

    printf("\n"); //  此时应该看到输出为 0 1 2 3 4 5 6 7 8 9
    quick_sort(a,10);

    for(int i=0; i<10; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    // 定义 int c[], int d[]，并初始化，用于测试quick_sort和heap_sort

    heap_sort(a,10);
    for(int i=0; i<10; i++) {
        printf("%d ", a[i]);
    }


}